﻿#pragma once

#include "kernel.h"

#define SIGN(a) (a) > 0 ? 1 : 0

namespace CAGD
{

class Convex
{
  public:
    /**
     * @brief 判断点是否在平面点集的凸包中.
     * @return
     * @param p
     * @param hull
     * @see
     */
    template <class T> static bool InConvexHull(BPntT<T> p, const std::vector<BPntT<T>> &hull)
    {
        // 利用二分角检测
        int n = hull.size();

        // 分离其它情况
        if (n == 0)
            return false;
        if (n == 1)
            return p == hull[0];
        if (n == 2)
            return on_line(p, hull[0], hull[1]);

        // 检查点的顺序是逆时针还是顺时针
        int a = 1, b = n - 1;
        BVecT<T> p0 = p - hull[0];
        BVecT<T> pa = hull[a] - hull[0];
        BVecT<T> pb = hull[b] - hull[0];

        // 叉积作为法向
        BVecT<T> normal = (pa % pb);

        // 循环直到两边界点相邻
        while (abs(a - b) > 1)
        {
            // 获得等分点与初始顶点的向量
            int mid = (a + b) / 2;
            BVecT<T> m0 = hull[mid] - hull[0];
            T sign = (p0 % m0) * normal;

            // 判断如果恰好在连线上，就计算距离，如果距离满足直线关系，就说明在内部
            if (fabs(sign) < CAGD_ABS_ACC)
            {
                if (fabs(hull[0].Distance(p) + hull[mid].Distance(p) - hull[0].Distance(hull[mid])) < CAGD_ABS_ACC)
                    return true;
                else
                    return false;
            }

            // 检查点在等分线的哪一侧，同时划分多边形
            if (sign > 0)
                b = mid;
            else
                a = mid;
        }

        // 剩下的一定是三角形，只要判断是否在三角形内部
        BVecT<T> p0pa = (hull[0] - p) % (hull[a] - p);
        BVecT<T> papb = (hull[a] - p) % (hull[b] - p);
        BVecT<T> pbp0 = (hull[b] - p) % (hull[0] - p);

        // 如果向量方向不同，说明在外部
        int s1 = SIGN(p0pa * papb);
        int s2 = SIGN(papb * pbp0);
        int s3 = SIGN(pbp0 * p0pa);
        if (s1 == s2 && s2 == s3)
            return true;

        return false;
    }

    /**
     * @brief 计算并返回平面多边形的凸包.
     * @return
     * @param polygon
     * @see
     */
    template <class T> static std::vector<BPnt2dT<T>> ConvexHull(const std::vector<BPnt2dT<T>> &polygon)
    {
        // 按照顺序检查相邻两个边向量的叉积的符号，如果出现符号反转，说明两个边的公共顶点“凹陷“，将异号的顶点移除后得到凸包
        std::vector<BPnt2dT<T>> hull = polygon;

        // 三角形一定是凸包，作为退出条件
        while (hull.size() > 3)
        {
            int n = hull.size();

            std::vector<BVec2dT<T>> pro(n);
            for (int i = 0; i < n; i++)
            {
                // 获得前后两个顶点的索引
                int indp1 = (i - 1 + n) % n;
                int indp2 = (i + 1) % n;
                BVec2dT<T> p1 = hull[indp1] - hull[i];
                BVec2dT<T> p2 = hull[i] - hull[indp2];

                // 保存叉积结果
                pro[i] = p1 % p2;
            }

            // 检查这些叉积的方向，同时统计符号
            int pos = 1;
            std::vector<int> index(n);
            for (int i = 1; i < n; i++)
            {
                // 全与第一个叉积做点积获得符号
                index[i] = SIGN(pro[i] * pro[0]);
                if (index[i] > 0)
                    pos++;
            }

            // 如果全部同号，说明已经形成凸包
            if (pos == n)
                break;

            // 删除对应少数的符号
            int sign = (pos > (n - pos)) ? -1 : 1;
            auto it = hull.begin();
            for (int i = 0; i < n; i++)
            {
                if (index[i] == sign)
                    it = hull.erase(it);
                else
                    it++;
            }
        }
        return hull;
    }

    /**
     * @brief 计算 q 沿着 v 方向投影后与凸包 hull 是否相交.
     * @return
     * @param q
     * @param v
     * @param hull
     * @see
     */
    template <class T> static bool InProjectHull(BPntT<T> q, BVec v, std::vector<BPntT<T>> &hull)
    {
        auto n = ((hull[1] - hull[0]) % (hull[2] - hull[1]));

        // 确保在射线方向上相交，排除相反方向
        T t = (n * (hull[0] - q)) / (n * v);
        if (t <= 0)
            return false;
        BPntT<T> inter = q + v * t;

        return InConvexHull(inter, hull);
    }
};

} // namespace CAGD

#undef SIGN
